#ifndef MAX_HEAP_H
#define MAX_HEAP_H
#include<iostream>

using namespace std;

static const int MaxCapacity = 30;

template <class T>
class max_heap
{
public:
    max_heap();
    max_heap(int capacity);
    ~max_heap();

    // 返回data在二叉堆中的索引
    int getIndex(T data);
    // 删除最大堆中的data
    int remove(T data);
    // 将data插入到二叉堆中
    int insert(T data);
    // 打印二叉堆
    void print();

private:
       // 最大堆的向下调整算法
       void filterdown(int start, int end);
       // 最大堆的向上调整算法(从start开始向上直到0，调整堆)
       void filterup(int start);

private:
    T *m_Heap;  // 数据
    int m_nCapacity;  // 总的容量
    int m_nSize;    // 实际容量
};

template <class T>
max_heap<T>::max_heap()
{
    max_heap(30);
}

template <class T>
max_heap<T>::max_heap(int capacity)
{
    cout << capacity << endl;
    m_nCapacity = capacity;
    m_nSize = 0;
    m_Heap = new T[m_nCapacity];
    cout << "good" << endl;
}

template <class T>
max_heap<T>::~max_heap()
{
    m_nCapacity = 0;
    m_nSize = 0;
    delete []m_Heap;
}

template <class T>
int max_heap<T>::getIndex(T data)
{
    int index = -1;
    for(auto i = 0; i < m_nSize; ++i)
    {
        if(data == m_Heap[i])
        {
            index = i;
            break;
        }
    }

    return index;
}

template <class T>
int max_heap<T>::remove(T data)
{
    int index = -1;
    if( m_nSize == 0)
        return index;

    index = getIndex(data);
    if(index == -1)
        return index;

    m_Heap[index] = m_Heap[--m_nSize];
    filterdown(index, m_nSize - 1);

    return 0;
}

template <class T>
int max_heap<T>::insert(T data)
{
    if(m_nSize == m_nCapacity)
        return -1;

    m_Heap[m_nSize] = data;
    filterup(m_nSize);
    ++m_nSize;

    return 0;
}

template <class T>
void max_heap<T>::print()
{
    for (int i = 0; i < m_nSize; i++)
        cout << m_Heap[i] << " ";
}

template <class T>
void max_heap<T>::filterdown(int start, int end)
{
    int c = start;
    int left = 2 * c + 1;
    int right = left + 1;
    T tmp = m_Heap[c];

    while(right <= end)
    {
        int max_index = m_Heap[left] > m_Heap[right] ? left : right;
        if(tmp >= m_Heap[max_index])
            break;
        m_Heap[c] = m_Heap[max_index];
        c = max_index;
        left = 2 * c + 1;
        right = left + 1;
    }

     m_Heap[c] = tmp;
}

template <class T>
void max_heap<T>::filterup(int start)
{
    int cur = start;
    int parent = (cur - 1) / 2;
    T tmp = m_Heap[cur];

    while(cur > 0)
    {
        if( m_Heap[parent] >= tmp )
            break;

        m_Heap[cur] = m_Heap[parent];
        cur = parent;
        parent = (cur - 1) / 2;
    }

    m_Heap[cur] = tmp;
}

#endif // MAX_HEAP_H
